package lcweekfight.w_384;

public class Code02_100145 {
    public int countCompleteSubstrings(String word, int k) {
        //0.生成前缀数组 //O(n)
        //1.划分子串 满足条件2
        //2.在大子串中 跑完全子字符串 26
        //0
        char[] str = word.toCharArray();
        int[][] pre = getpre(str);
        int res = 0;
        for (int i = 0, j = 0, n = word.length(); i < n;) {
            while (j + 1 < n  && (Math.abs(str[j + 1] - str[j]) <= 2)){
                j++;
            }
            res += getRes(str,i,j,k,pre);
            while(i <= j){
                i++;
            }
            i = ++j;
        }
        return res;
    }
    public int getRes(char[] str,int L,int R,int k,int[][] pre){
        int res = 0;
        for (int len = k; len <= R - L + 1 && len <= 26 * k; len += k) {
            for (int l = L, r = L + len - 1; r <= R; l++, r++) {//子串s[l,r]
                boolean can = true;
                for (int i = 0; i < 26; i++) {
                    if (getCharNum(pre,l,r,i) != 0 && getCharNum(pre,l,r,i) != k) {
                        can = false;
                        break;
                    }
                }
                if (can){
                    res++;
                }
            }
        }
        return res;
    }
    public int[][] getpre(char[] str){
        int N = str.length;
        int[][] res = new int[N + 1][26];
        for(int i = 0;i < 26;i++){
            res[0][i] = 0;
        }
        for(int i = 0;i < N;i++){
            for (int j = 0; j < 26; j++){
                res[i + 1][j] = res[i][j] + (str[i] - 'a' == j ?1 : 0);
            }
        }
        return res;
    }
    public int getCharNum(int[][] pre,int L,int R,int c){
        return pre[R + 1][c] - pre[L][c];
    }
}
